package leetcode.code;

import java.util.ArrayList;
import java.util.List;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

/**
 * 282. 给表达式添加运算符
 *
 * @author CaoYu
 * @date 2021年10月16日
 * @description
 */
public class Solution282_4 implements IDebug {

	private int target;// 目标值
	private List<String> ans;// 答案
	private char[] nums;// num中间加空格
	private int len;// nums数组长度
	private char[] buffer;

	public List<String> addOperators(String num, int target) {
		ans = new ArrayList<>();
//		if (num.length() == 1) {
//			if (target == Integer.valueOf(num)) {
//				ans.add(num);
//			}
//			return ans;
//		}
		this.target = target;// 设置目标
		this.len = num.length();
		this.nums = num.toCharArray();
		this.buffer = new char[len << 1];
		f(0, 0, 0, 0, null, '+');
		return ans;
	}

	private void f(int i, int j, int p, long ans, Long mul, char op) {
		buffer[p] = nums[i];
		long curNum = Long.valueOf(new String(nums, j, i - j + 1));
		long curAns = 0;
		Long curMul = null;
		if (op == '+') {
			curAns = ans + curNum;
			curMul = curNum;
		} else if (op == '-') {
			curAns = ans - curNum;
			curMul = -curNum;
		} else if (op == '*') {
			curAns = ans - mul + mul * curNum;
			curMul = mul * curNum;//就差这了
		}
		if (i == len - 1) {
			if (curAns == target) {
				this.ans.add(new String(buffer, 0, p + 1));
			}
			return;
		}
		if (nums[j] != '0') {
			f(i + 1, j, p + 1, ans, mul, op);
		}
		buffer[p + 1] = '-';
		f(i + 1, i + 1, p + 2, curAns, curMul, '-');
		buffer[p + 1] = '+';
		f(i + 1, i + 1, p + 2, curAns, curMul, '+');
		buffer[p + 1] = '*';
		f(i + 1, i + 1, p + 2, curAns, curMul, '*');
	}

	public static void main(String[] args) {
		Solution282_4 so = new Solution282_4();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();
		so.debug6();
		so.debug7();
	}

	@Override
	public void debug1() {
		String num = "123";
		int target = 6;
		String str = "[\"1+2+3\", \"1*2*3\"]";
		List<String> e = HelpDebug.str2liststr(str);
		List<String> r = this.addOperators(num, target);
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug2() {
		String num = "232";
		int target = 8;
		String str = "[\"2*3+2\", \"2+3*2\"]";
		List<String> e = HelpDebug.str2liststr(str);
		List<String> r = this.addOperators(num, target);
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug3() {
		String num = "00";
		int target = 0;
		String str = "[\"0+0\", \"0-0\", \"0*0\"]";
		List<String> e = HelpDebug.str2liststr(str);
		List<String> r = this.addOperators(num, target);
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug4() {
		String num = "105";
		int target = 5;
		String str = "[\"1*0+5\",\"10-5\"]";
		List<String> e = HelpDebug.str2liststr(str);
		List<String> r = this.addOperators(num, target);
		HelpDebug.compare(e, r);
	}

	public void debug5() {
		String num = "3456237490";
		int target = 9191;
		String str = "[]";
		List<String> e = HelpDebug.str2liststr(str);
		List<String> r = this.addOperators(num, target);
		HelpDebug.compare(e, r);
	}

	public void debug6() {
		String num = "9999999999";
		int target = 1409865409;
		String str = "[]";
		List<String> e = HelpDebug.str2liststr(str);
		List<String> r = this.addOperators(num, target);
		HelpDebug.compare(e, r);
	}

	public void debug7() {
		String num = "123456789";
		int target = 45;
		String str = "[\"1*2*3*4*5-6-78+9\",\"1*2*3*4+5+6-7+8+9\",\"1*2*3+4+5+6+7+8+9\",\"1*2*3+4+5-6*7+8*9\",\"1*2*3+4-5*6+7*8+9\",\"1*2*3+4-5*6-7+8*9\",\"1*2*3-4*5+6*7+8+9\",\"1*2*3-4*5-6+7*8+9\",\"1*2*3-4*5-6-7+8*9\",\"1*2*3-45+67+8+9\",\"1*2*34+56-7-8*9\",\"1*2*34-5+6-7-8-9\",\"1*2+3*4-56+78+9\",\"1*2+3+4+5*6+7+8-9\",\"1*2+3+4-5+6*7+8-9\",\"1*2+3+4-5-6+7*8-9\",\"1*2+3+45+67-8*9\",\"1*2+3-45+6+7+8*9\",\"1*2+34+5-6-7+8+9\",\"1*2+34+56-7*8+9\",\"1*2+34-5+6+7-8+9\",\"1*2+34-56+7*8+9\",\"1*2+34-56-7+8*9\",\"1*2-3*4+5+67-8-9\",\"1*2-3+4-5-6*7+89\",\"1*2-3-4*5+67+8-9\",\"1*2-3-4+56-7-8+9\",\"1*2-34+5*6+7*8-9\",\"1*23+4*5-6+7-8+9\",\"1*23-4-56-7+89\",\"1+2*3*4*5+6+7-89\",\"1+2*3*4+5*6+7-8-9\",\"1+2*3*4-5+6*7-8-9\",\"1+2*3+4*5*6+7-89\",\"1+2*3+4*5-6+7+8+9\",\"1+2*3-4-5-6*7+89\",\"1+2*34-5*6+7+8-9\",\"1+2+3*4*5+6-7-8-9\",\"1+2+3*4+5+6*7-8-9\",\"1+2+3*45-6-78-9\",\"1+2+3+4+5+6+7+8+9\",\"1+2+3+4+5-6*7+8*9\",\"1+2+3+4-5*6+7*8+9\",\"1+2+3+4-5*6-7+8*9\",\"1+2+3-4*5+6*7+8+9\",\"1+2+3-4*5-6+7*8+9\",\"1+2+3-4*5-6-7+8*9\",\"1+2+3-45+67+8+9\",\"1+2-3*4*5+6+7+89\",\"1+2-3*4+5*6+7+8+9\",\"1+2-3*4-5+6*7+8+9\",\"1+2-3*4-5-6+7*8+9\",\"1+2-3*4-5-6-7+8*9\",\"1+2-3+4*5+6*7-8-9\",\"1+2-3+45+6-7-8+9\",\"1+2-3+45-6+7+8-9\",\"1+2-3-4-5*6+7+8*9\",\"1+2-3-45-6+7+89\",\"1+2-34+5+6+7*8+9\",\"1+2-34+5+6-7+8*9\",\"1+2-34-5-6+78+9\",\"1+23*4+5-6-7*8+9\",\"1+23*4-5-6*7+8-9\",\"1+23*4-56+7-8+9\",\"1+23+4+5+6+7+8-9\",\"1+23+4-5*6+7*8-9\",\"1+23+4-5-67+89\",\"1+23-4*5+6*7+8-9\",\"1+23-4*5-6+7*8-9\",\"1+23-4-5+6+7+8+9\",\"1+23-4-5-6*7+8*9\",\"1+23-45+67+8-9\",\"1-2*3*4+5-6+78-9\",\"1-2*3*4-5-6+7+8*9\",\"1-2*3+4*5+6+7+8+9\",\"1-2*3+4*5-6*7+8*9\",\"1-2*3+4+5+6*7+8-9\",\"1-2*3+4+5-6+7*8-9\",\"1-2*3+4+56+7-8-9\",\"1-2*3+45-67+8*9\",\"1-2*3-4+5*6+7+8+9\",\"1-2*3-4-5+6*7+8+9\",\"1-2*3-4-5-6+7*8+9\",\"1-2*3-4-5-6-7+8*9\",\"1-2*34+5*6-7+89\",\"1-2+3*4*5-6-7+8-9\",\"1-2+3+4-5*6+78-9\",\"1-2+3+45+6-7+8-9\",\"1-2+3-4*5-6+78-9\",\"1-2+3-45+6-7+89\",\"1-2-3*4+5+6+7*8-9\",\"1-2-3*4-5-6+78-9\",\"1-2-3+4-5+67-8-9\",\"1-2-3+45-6-7+8+9\",\"1-2-34+5+6+78-9\",\"1-2-34+56+7+8+9\",\"1-2-34-5+6+7+8*9\",\"1-23*4+5+6*7+89\",\"1-23+4*5-6*7+89\",\"1-23+4-5+67-8+9\",\"1-23+45-67+89\",\"1-23-4+5+67+8-9\",\"1-23-4-5-6-7+89\",\"12*3*4-5*6-78+9\",\"12*3+4+5+6-7-8+9\",\"12*3+4+5-6+7+8-9\",\"12*3-4-5-6+7+8+9\",\"12*3-4-56+78-9\",\"12+3*4+5+6-7+8+9\",\"12+3*45-6-7-89\",\"12+3+4-56-7+89\",\"12+3-4*5+67-8-9\",\"12+3-45+6+78-9\",\"12+34-5-6-7+8+9\",\"12-3*4*5+6+78+9\",\"12-3*4-5+67-8-9\",\"12-3+4*5+6-7+8+9\",\"12-3+4+56-7-8-9\",\"12-3-4+5*6-7+8+9\",\"12-3-4-56+7+89\",\"12-3-45-6+78+9\"]";
		List<String> e = HelpDebug.str2liststr(str);
		List<String> r = this.addOperators(num, target);
		HelpDebug.compare(e, r);
	}

}
